#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution
{
public:
    int purchasePlans(vector<int> &nums, int target)
    {
        long long res = 0;
        long long mod = 1000000007;
        sort(nums.begin(), nums.end());
        int i = 0, j = nums.size() - 1;
        for (i = 0; i < j; i++)
        {
            while (j > i && nums[i] + nums[j] > target)
            {
                j--;
            }
            res += j - i;
        }
        return res % mod;
    }
    int purchasePlans_2(vector<int> &nums, int target)
    {
        int record[100001] = {0};
        for (auto price : nums)
        {
            record[price]++;
        }
        long same = 0, different = 0;
        for (int i = 1; (i < 100001) && (i < target); i++)
        {
            if ((i << 1) <= target)
            {
                same += static_cast<long>(record[i]) * (record[i] - 1) / 2;
                different += static_cast<long>(record[i]) * (record[i - 1]);
            }
            else
            {
                different += static_cast<long>(record[i]) * (record[target - i]);
            }
            record[i] += record[i - 1];
        }
        return (same + different) % 1000000007;
    }
};
int main()
{
    Solution s;
    return 0;
}